package Leetcode.DayTest;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @Author: kirito
 * @Date: 2024/10/28 12:02
 * @Description:
 */

public class 字母移位_差分 {
    /**
     * 有一个由小写字母组成的字符串 s，和一个长度相同的整数数组 shifts。
     *
     * 我们将字母表中的下一个字母称为原字母的 移位 shift() （由于字母表是环绕的， 'z' 将会变成 'a'）。
     *
     * 例如，shift('a') = 'b', shift('t') = 'u', 以及 shift('z') = 'a'。
     * 对于每个 shifts[i] = x ， 我们会将 s 中的前 i + 1 个字母移位 x 次。
     *
     * 返回 将所有这些移位都应用到 s 后最终得到的字符串 。
     *
     *
     * 输入：s = "abc", shifts = [3,5,9]
     * 输出："rpl"
     * 解释：
     * 我们以 "abc" 开始。
     * 将 S 中的第 1 个字母移位 3 次后，我们得到 "dbc"。
     * 再将 S 中的前 2 个字母移位 5 次后，我们得到 "igc"。
     * 最后将 S 中的这 3 个字母移位 9 次后，我们得到答案 "rpl"。
     *
     * 采用从右往左遍历的后缀和，然后对26取余即可
     */
    public String shiftingLetters(String s, int[] shifts) {
        int n = s.length();
        int[] accumulatedShifts = new int[n];
        accumulatedShifts[n - 1] = shifts[n - 1] % 26;
        for (int i = n - 2; i >= 0; i--) {
            accumulatedShifts[i] = (accumulatedShifts[i + 1] + shifts[i]) % 26;
        }
        StringBuffer sb = new StringBuffer();
        for (int i = 0; i < n; i++) {
            int index = s.charAt(i) - 'a';
            index = (index + accumulatedShifts[i]) % 26;
            sb.append((char) ('a' + index));
        }
        return sb.toString();
    }

    /**
     * 给你一个小写英文字母组成的字符串 s 和一个二维整数数组 shifts ，
     * 其中 shifts[i] = [starti, endi, directioni] 。
     * 对于每个 i ，将 s 中从下标 starti 到下标 endi （两者都包含）所有字符都进行移位运算，
     * 如果 directioni = 1 将字符向后移位，如果 directioni = 0 将字符向前移位。
     *
     * 输入：s = "abc", shifts = [[0,1,0],[1,2,1],[0,2,1]]
     * 输出："ace"
     * 解释：首先，将下标从 0 到 1 的字母向前移位，得到 s = "zac" 。
     * 然后，将下标从 1 到 2 的字母向后移位，得到 s = "zbd" 。
     * 最后，将下标从 0 到 2 的字符向后移位，得到 s = "ace" 。
     *
     * 差分的思想，感觉还不是太熟练，能想到这么做，但是不怎么会写
     *
     * 前缀和主要适用的场景是原始数组不会被修改的情况下，频繁查询某个区间的累加和
     *
     * 差分数组的主要适用场景是频繁对原始数组的某个区间的元素进行增减
     *
     * 使用场景：对于一个数组 nums[]
     *
     * 要求一：对 num[2...4] 全部 + 1
     * 要求二：对 num[1...3] 全部 - 3
     * 要求三：对 num[0...4] 全部 + 9
     * 看到上述情景，首先想到的肯定是遍历（bao li）。直接对数组循环 3 遍，
     * 每次在规定的区间上按要求进行操作，此时时间复杂度 O(3n)
     *
     * 但是当这样的操作变得频繁后，时间复杂度也呈线性递增
     *
     */
    public String shiftingLetters(String s, int[][] shifts) {
        /*
        差分数组:
        将移位区间的代数和用差分数组求出来，然后最后进行转化即可
         */
        int MOD = 260000;
        int n = s.length();
        int[] diff = new int[n + 1];
        for (int[] shift : shifts) {
            int num = shift[2] == 0 ? -1 : 1;
            diff[shift[0]] += num;
            diff[shift[1] + 1] -= num;
        }
        // 前缀和就是该区间内的数字之和
        int cur = 0;
        for (int i = 0; i < n; i++) {
            cur += diff[i];
            diff[i] = cur;
        }
        // 进行构建
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            // 注意取余操作，要化为正数再进行取余
            sb.append((char) ('a' + ((s.charAt(i) - 'a' + MOD) + diff[i]) % 26));
        }
        return sb.toString();
    }

    /**
     * 给你一个下标从 0 开始的整数数组 nums 。请你从 nums 中找出和 最大 的一对数，
     * 且这两个数数位上最大的数字相等。
     *
     * 返回最大和，如果不存在满足题意的数字对，返回 -1 。
     *
     *
     * 输入：nums = [51,71,17,24,42]
     * 输出：88
     * 解释：
     * i = 1 和 j = 2 ，nums[i] 和 nums[j] 数位上最大的数字相等，且这一对的总和 71 + 17 = 88 。
     * i = 3 和 j = 4 ，nums[i] 和 nums[j] 数位上最大的数字相等，且这一对的总和 24 + 42 = 66 。
     * 可以证明不存在其他数对满足数位上最大的数字相等，所以答案是 88 。
     */
    public int maxSum(int[] nums) {
        int ans = -1;
        //记录每个数位对应的最大的数是多少  例如：71  数位最大是7，那么7对应的最大值就是71
        //后序如果还有数位最大值是7的数，满足题目要求，进行求和操作，保留ans最大值，更新maxVal即可
        int[] maxVal = new int[10];
        Arrays.fill(maxVal, Integer.MIN_VALUE);
        for (int num : nums) {
            int maxD = 0;
            //计算每个数 最大的数位是多少
            for (int x = num; x > 0; x /= 10) {
                maxD = Math.max(maxD, x % 10);
            }
            ans = Math.max(ans, num + maxVal[maxD]);
            maxVal[maxD] = Math.max(maxVal[maxD], num);
        }
        return ans;
    }

    /**
     * 给你一个整数数组 nums 。请你创建一个满足以下条件的二维数组：
     *
     * 二维数组应该 只 包含数组 nums 中的元素。
     * 二维数组中的每一行都包含 不同 的整数。
     * 二维数组的行数应尽可能 少 。
     * 返回结果数组。如果存在多种答案，则返回其中任何一种。
     *
     * 请注意，二维数组的每一行上可以存在不同数量的元素。
     *
     *
     * 输入：nums = [1,3,4,1,2,3,1]
     * 输出：[[1,3,4,2],[1,3],[1]]
     * 解释：根据题目要求可以创建包含以下几行元素的二维数组：
     * - 1,3,4,2
     * - 1,3
     * - 1
     * nums 中的所有元素都有用到，并且每一行都由不同的整数组成，所以这是一个符合题目要求的答案。
     * 可以证明无法创建少于三行且符合题目要求的二维数组。
     *
     1 <= nums.length <= 200
     1 <= nums[i] <= nums.length

     感觉可以用计数排序的思想
     初始化200的数组，统计每个数字出现的次数
     然后一直遍历，如果次数>1就添加到list里边，然后次数--
     直到所有的次数均为0就跳出循环
     */
    public List<List<Integer>> findMatrix(int[] nums) {
        List<List<Integer>> ans = new ArrayList<>();
        int[] arr = new int[201];
        int len = nums.length;
        for (int i = 0; i < len; i++) {
            arr[nums[i]]++;
        }
        while (len > 0) {
            List<Integer> list = new ArrayList<>();
            for (int i = 0; i < 201; i++) {
                if (arr[i] > 0) {
                    list.add(i);
                    arr[i]--;
                    len--;
                }
            }
            ans.add(list);
        }
        return ans;
    }

    /**
     * 你和朋友们准备去野炊。给你一个下标从 0 开始的整数数组 security ，其中 security[i] 是第 i 天的建议出行指数。日子从 0 开始编号。同时给你一个整数 time 。
     *
     * 如果第 i 天满足以下所有条件，我们称它为一个适合野炊的日子：
     *
     * 第 i 天前和后都分别至少有 time 天。
     * 第 i 天前连续 time 天建议出行指数都是非递增的。
     * 第 i 天后连续 time 天建议出行指数都是非递减的。
     * 更正式的，第 i 天是一个适合野炊的日子当且仅当：security[i - time] >= security[i - time + 1] >= ... >= security[i] <= ... <= security[i + time - 1] <= security[i + time].
     *
     * 请你返回一个数组，包含 所有 适合野炊的日子（下标从 0 开始）。返回的日子可以 任意 顺序排列。
     *
     *
     * 输入：security = [5,3,3,3,5,6,2], time = 2
     * 输出：[2,3]
     * 解释：
     * 第 2 天，我们有 security[0] >= security[1] >= security[2] <= security[3] <= security[4] 。
     * 第 3 天，我们有 security[1] >= security[2] >= security[3] <= security[4] <= security[5] 。
     * 没有其他日子符合这个条件，所以日子 2 和 3 是适合野炊的日子。
     */
    public List<Integer> goodDaysToRobBank(int[] security, int time) {
        //dp
        int n = security.length;
        int[] left = new int[n];
        int[] right = new int[n];
        for (int i = 1; i < n; i++) {
            if (security[i] <= security[i - 1]) {
                left[i] = left[i - 1] + 1;
            }
            if (security[n - i - 1] <= security[n - i]) {
                right[n - i - 1] = right[n - i] + 1;
            }
        }

        List<Integer> ans = new ArrayList<>();
        for (int i = time; i < n - time; i++) {
            if (left[i] >= time && right[i] >= time) {
                ans.add(i);
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        字母移位_差分 test = new 字母移位_差分();
    }
}
